package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;
import java.util.ArrayList;
import java.util.List;

/**
 * 图的深度优先遍历实现
 *
 * @author initcap
 * @date Created in 7/31/19 9:54 AM.
 */
public class GraphDfs {

    private Graph<Integer, Double> graph;
    private boolean[] visited;
    private List<Integer> pre;
    private List<Integer> post;

    public GraphDfs(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.nodeSize()];
        post = new ArrayList<>(graph.nodeSize());
        pre = new ArrayList<>(graph.nodeSize());
        for (int i = 0; i < graph.nodeSize(); i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new SparseGraph("algorithm/testG10.txt", false);
        GraphDfs dfs = new GraphDfs(graph);
        System.out.println("DFS pre : " + dfs.pre());
        System.out.println("DFS post : " + dfs.post());
    }

    private void dfs(int v) {
        visited[v] = true;
        pre.add(v);
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
        post.add(v);
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }

}
